module Busqueda (búsquedaDelTesoro) where

import Diccionario
import Maybe

{- obtiene los primeros elementos de una lista, hasta que se cumple cierto predicado.
   el último elemento que se deja es el primero que cumple dicho predicado.
   ejemplo: takeUntil (==3) [1..] = [1,2,3] -}
takeUntil :: (a -> Bool) -> [a] -> [a]
takeUntil ultimo = foldr (\x rest -> if (ultimo x) then [x] else x:rest) []

{- realiza la búsqueda del tesoro.
   idea:    se construye la lista de resultados comenzando por la pista,
            hasta encontrar el tesoro o que ya no se pueda seguir.
            luego se queda con el último elemento -}
búsquedaDelTesoro :: Eq a => a -> (a -> Bool) -> Diccionario a a -> Maybe a 
búsquedaDelTesoro pista esTesoro dicc = last (takeUntil tesoroOFin (iterate buscarEnDic (obtener pista dicc)))
    where   
            {- asume que el argumento no es Nothing, y retorna 
               el resultado de busca el elemento en el diccionario -}
            buscarEnDic = (flip obtener dicc).fromJust
            {- busco en el diccionario hasta que no encuentro
               una clave o encontré el tesoro -}
            tesoroOFin m = isNothing m || esTesoro (fromJust m)